1926F - Vlad and Avoiding X - CodeForces Solution

#include <bits/stdc++.h>

using namespace std;

int f[7][1 << 12];
int tr[1 << 12][1 << 7];
int col[7];
char s[10];

vector<int> state;

void solve() {
    for (int i = 0; i < 7; ++i) {
        scanf("%s", s);
        col[i] = 0;
        for (int j = 0; j < 7; ++j)
            col[i] |= (s[j] == 'B') << j;
    }
    memset(f, 32, sizeof f);
    for (int mask = 0; mask < (1 << 7); ++mask)
        if((mask | col[0]) == col[0])
            f[0][mask << 5] = __builtin_popcount(mask ^ col[0]);
    for (int i = 1; i < 7; ++i) {
        for (int mask1 : state) if (f[i - 1][mask1] <= 49) {
            for (int mask2 = col[i]; ; mask2 = mask2 - 1 & col[i]) {
                int mask3 = tr[mask1][mask2];
                if (mask3 == -1) continue;
                f[i][mask3] = min(f[i][mask3], f[i - 1][mask1] + __builtin_popcount(mask2 ^ col[i]));
                if (mask2 == 0) break;
            }
        }
    }
    int ans = 49;
    for (int mask : state)
        ans = min(ans, f[6][mask]);
    printf("%d\n", ans);
}

int main() {
    for (int mask1 = 0; mask1 < (1 << 7); ++mask1)
        for (int mask2 = 0; mask2 < (1 << 7); ++mask2) {
            int mask3 = mask2 << 5;
            for (int i = 1; i <= 5; ++i) if (mask2 >> i & 1)
                if ((mask1 >> i - 1 & 1) && (mask1 >> i + 1 & 1)) {
                    mask3 |= 1 << i - 1;
                }
            state.push_back(mask3);
        }
    sort(state.begin(), state.end());
    state.resize(unique(state.begin(), state.end()) - state.begin());
    cerr << state.size() << endl;
    for (int mask1 : state)
        for (int mask3 = 0; mask3 < (1 << 7); ++mask3) {
            bool flag = 1;
            for (int i = 1; i <= 5; ++i) if(mask1 >> i - 1 & 1) {
                if ((mask3 >> i - 1 & 1) && (mask3 >> i + 1 & 1)) {
                    flag = false;
                    break;
                }
            }
            if (!flag) tr[mask1][mask3] = -1;
            else {
                int mask4 = mask3 << 5;
                for (int i = 1; i <= 5; ++i) if (mask3 >> i & 1)
                    if ((mask1 >> 5 >> i - 1 & 1) && (mask1 >> 5 >> i + 1 & 1)) {
                        mask4 |= 1 << i - 1;
                    }
                tr[mask1][mask3] = mask4;
            }
        }
    int T;
    scanf("%d", &T);
    while (T--) solve();
    system("pause");
    return 0;
}